/*
 * @lc app=leetcode.cn id=438 lang=cpp
 *
 * [438] 找到字符串中所有字母异位词
 *
 * 方法1：使用 int[26] 作为hash表，逐帧移动窗口
 * - 不要因为窗口移动就陷入思考死循环
 * - 使用大小相同的 vector<int>(26) 可以直接进行比较，但是时间开销更大
 *
 * 方法2（官方题解）：优化滑动窗口 -> 优化子串匹配
 * - 引入变量 differ 来记录当前窗口与字符串 p 中数量不同的字母的个数，并在滑动窗口的过程中维护它
 * - 在判断滑动窗口中每种字母的数量与字符串 p 中每种字母的数量是否相同时，只需要判断 differ 是否为零即可
 */

#include <vector>
#include <string>
#include <iostream>

// @lc code=start
class Solution
{
public:
    inline bool matchSubStr(int a[], int b[])
    {
        for (int i = 0; i < 26; i++)
            if (a[i] != b[i])
                return false;
        return true;
    }

    std::vector<int> findAnagrams_01(std::string s, std::string p)
    {
        std::vector<int> result;
        int freq_s[26] = {0};
        int freq_p[26] = {0};

        const int len_s = s.size();
        const int len_p = p.size();
        if (len_s < len_p)
            return result;

        for (int i = 0; i < len_p; i++)
        {
            freq_s[s[i] - 'a']++;
            freq_p[p[i] - 'a']++;
        }

        /* 滑动窗口 */
        int front = 0, rear = len_p;
        while (true)
        {
            /* 子串匹配 */
            if (matchSubStr(freq_s, freq_p))
                result.push_back(front);

            /* 窗口移动 */
            if (rear < len_s)
            {
                freq_s[s[front] - 'a']--;
                front++;
                freq_s[s[rear] - 'a']++;
                rear++;
            }
            else
                break;
        }

        return result;
    }

    std::vector<int> findAnagrams_02(std::string s, std::string p)
    {
        std::vector<int> result;

        const int len_s = s.size();
        const int len_p = p.size();
        if (len_s < len_p)
            return result;

        int count[26] = {0}; // 统计 s 与 p 的字符差异
        for (int i = 0; i < len_p; i++)
        {
            count[s[i] - 'a']++;
            count[p[i] - 'a']--;
        }

        int differ = 0; // 记录当前窗口与 p 中数量不同的字母的个数
        for (int i = 0; i < 26; i++)
        {
            if (count[i] != 0)
                differ++;
        }
        if (differ == 0) // 第一个子串情况
            result.push_back(0);

        /* 滑动窗口 */
        for (int i = 0; i < len_s - len_p; i++)
        {
            /* 把左端滑出窗口 */
            count[s[i] - 'a']--;
            if (count[s[i] - 'a'] == 0) // 不同 -> 相同
                differ--;
            else if (count[s[i] - 'a'] == -1) // 相同 -> 不同
                differ++;

            /* 把右端窗口滑入 */
            count[s[i + len_p] - 'a']++;
            if (count[s[i + len_p] - 'a'] == 0) // 不同 -> 相同
                differ--;
            else if (count[s[i + len_p] - 'a'] == 1) // 相同 -> 不同
                differ++;

            if (differ == 0)
                result.push_back(i + 1);
        }

        return result;
    }
};
// @lc code=end

int main(void)
{
    Solution solution;
    std::string s("cbaebabacd");
    std::string p("abc");

    for (auto n : solution.findAnagrams_02(s, p))
        std::cout << n << " " << std::endl;

    return 0;
}